using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace EasyPath_CSharp
{

    class CollectionDiff<T>
    {
        public CollectionDiff(ICollection<T> leftOnly, ICollection<T> rightOnly, ICollection<T> both)
        {
            this.leftOnly = leftOnly;
            this.rightOnly = rightOnly;
            this.both = both;
        }
        public ICollection<T> leftOnly { get; set; }

        public ICollection<T> rightOnly { get; set; }

        public ICollection<T> both { get; set; }
    }

    class CollectionUtils
    {
        public static CollectionDiff<T> diff<T>(ICollection<T> left, ICollection<T> right)
        {
            var diffDict = new Dictionary<T, int>(left.Count);

            foreach(T t in left)
            {
                int i = 0;
                if(diffDict.ContainsKey(t))
                {
                    diffDict.TryGetValue(t, out i);
                    diffDict[t] = i - 1;
                } else
                {
                    diffDict.Add(t, i - 1);
                }
            }

            foreach(T t in right)
            {
                int i = 0;
                if (diffDict.ContainsKey(t))
                {
                    diffDict.TryGetValue(t, out i);
                    diffDict[t] = i + 1;
                } else
                {
                    diffDict.Add(t, i + 1);
                }
            }

            var leftOnly = new LinkedList<T>();
            var rightOnly = new LinkedList<T>();
            var both = new LinkedList<T>();

            foreach (var kv in diffDict)
            {
                var key = kv.Key;
                var value = kv.Value;

                switch(value)
                {
                    case -1:
                        leftOnly.AddLast(key);
                        break;

                    case 0:
                        both.AddLast(key);
                        break;

                    case 1:
                        rightOnly.AddLast(key);
                        break;
                }
            }

            return new CollectionDiff<T>(leftOnly, rightOnly, both);
        }
    }


    class KeyWithTwoValue<K, V>
    {
        private K key { get; set; }

        private V leftValue { get; set; }

        private V rightValue { get; set; }
    }
}
